//
//  ForEach.swift
//  OpenSwiftUICore
//
//  Audited for 6.5.4
//  Status: Blocked by Subview
//  ID: 1A3DD35AB7F6976908CD7AF959F34D1F (SwiftUICore)

import Foundation
package import OpenAttributeGraphShims
@_spi(OpenSwiftUI) import OpenObservation

// MARK: - ForEach

/// A structure that computes views on demand from an underlying collection of
/// identified data.
///
/// Use `ForEach` to provide views based on a
/// [RandomAccessCollection](https://developer.apple.com/documentation/swift/randomaccesscollection)
/// of some data type. Either the collection's elements must conform to
/// [Identifiable](https://developer.apple.com/documentation/swift/identifiable) or you
/// need to provide an `id` parameter to the `ForEach` initializer.
///
/// The following example creates a `NamedFont` type that conforms to
/// [Identifiable](https://developer.apple.com/documentation/swift/identifiable), and an
/// array of this type called `namedFonts`. A `ForEach` instance iterates
/// over the array, producing new ``Text`` instances that display examples
/// of each OpenSwiftUI ``Font`` style provided in the array.
///
///     private struct NamedFont: Identifiable {
///         let name: String
///         let font: Font
///         var id: String { name }
///     }
///
///     private let namedFonts: [NamedFont] = [
///         NamedFont(name: "Large Title", font: .largeTitle),
///         NamedFont(name: "Title", font: .title),
///         NamedFont(name: "Headline", font: .headline),
///         NamedFont(name: "Body", font: .body),
///         NamedFont(name: "Caption", font: .caption)
///     ]
///
///     var body: some View {
///         ForEach(namedFonts) { namedFont in
///             Text(namedFont.name)
///                 .font(namedFont.font)
///         }
///     }
///
/// ![A vertically arranged stack of labels showing various standard fonts,
/// such as Large Title and Headline.](OpenSwiftUI-ForEach-fonts.png)
///
/// Some containers like ``List`` or ``LazyVStack`` will query the elements
/// within a for each lazily. To obtain maximal performance, ensure that
/// the view created from each element in the collection represents a
/// constant number of views.
///
/// For example, the following view uses an if statement which means each
/// element of the collection can represent either 1 or 0 views, a
/// non-constant number.
///
///     ForEach(namedFonts) { namedFont in
///         if namedFont.name.count != 2 {
///             Text(namedFont.name)
///         }
///     }
///
/// You can make the above view represent a constant number of views by
/// wrapping the condition in a ``VStack``, an ``HStack``, or a ``ZStack``.
///
///     ForEach(namedFonts) { namedFont in
///         VStack {
///             if namedFont.name.count != 2 {
///                 Text(namedFont.name)
///             }
///         }
///     }
///
/// When enabling the following launch argument, OpenSwiftUI will log when
/// it encounters a view that produces a non-constant number of views
/// in these containers:
///
///     -LogForEachSlowPath YES
///
@available(OpenSwiftUI_v1_0, *)
public struct ForEach<Data, ID, Content> where Data: RandomAccessCollection, ID: Hashable {

    /// The collection of underlying identified data that OpenSwiftUI uses to create
    /// views dynamically.
    public var data: Data

    /// A function to create content on demand using the underlying data.
    public var content: (Data.Element) -> Content

    package enum IDGenerator {
        case keyPath(KeyPath<Data.Element, ID>)
        case offset

        package var isConstant: Bool {
            switch self {
            case .keyPath: false
            case .offset: true
            }
        }

        package func makeID(data: Data, index: Data.Index, offset: Int) -> ID {
            switch self {
            case let .keyPath(keyPath): data[index][keyPath: keyPath]
            case .offset: unsafeBitCast(offset, to: ID.self)
            }
        }
    }

    package var idGenerator: IDGenerator

    package var reuseID: KeyPath<Data.Element, Int>?

    var obsoleteContentID: Int

    package init(
        _ data: Data,
        idGenerator: IDGenerator,
        content: @escaping (Data.Element) -> Content
    ) {
        self.data = data
        self.idGenerator = idGenerator
        self.content = content
        self.obsoleteContentID = isLinkedOnOrAfter(.v6) ? .zero : UniqueID().value
    }

    package init<T>(
        _ other: ForEach<Data, ID, T>,
        transform: @escaping (T) -> Content
    ) {
        self.data = other.data
        self.idGenerator = switch other.idGenerator {
        case let .keyPath(keyPath): .keyPath(keyPath)
        case .offset: .offset
        }
        self.content = { element in
            transform(other.content(element))
        }
        self.obsoleteContentID = other.obsoleteContentID
    }
}

@available(*, unavailable)
extension ForEach: Sendable {}

// MARK: - ForEach + View [Blocked by Subview]

@available(OpenSwiftUI_v1_0, *)
extension ForEach: View, PrimitiveView where Content: View {
    public typealias Body = Never

    nonisolated public static func _makeView(
        view: _GraphValue<Self>,
        inputs: _ViewInputs
    ) -> _ViewOutputs {
        if let outputs = makeForEachView(view: view, inputs: inputs) {
            return outputs
        } else {
            return makeImplicitRoot(view: view, inputs: inputs)
        }
    }

    nonisolated static func makeForEachView(
        view: _GraphValue<Self>,
        inputs: _ViewInputs
    ) -> _ViewOutputs? {
        // TODO: Subview stuff
        return nil
    }

    nonisolated public static func _makeViewList(
        view: _GraphValue<Self>,
        inputs: _ViewListInputs
    ) -> _ViewListOutputs {
        if let outputs = makeForEachViewList(view: view, inputs: inputs) {
            return outputs
        } else {
            let state = ForEachState<Data, ID, Content>(inputs: inputs)
            let info = Attribute(
                ForEachState.Info.Init(
                    view: view.value,
                    state: state
                )
            )
            state.info = info
            let eviction = inputs.base[ForEachEvictionInput.self]
            if eviction != .init() || ForEachEvictionInput.evictByDefault {
                let evictor = Attribute(
                    ForEachState.Evictor(
                        state: state,
                        isEnabled: eviction,
                        updateSeed: GraphHost.currentHost.data.$updateSeed,
                    )
                )
                evictor.flags = .transactional
            }
            let list = Attribute(
                ForEachList.Init(
                    info: info,
                    seed: .zero
                )
            )
            state.list = list
            return .init(
                .dynamicList(list, nil),
                nextImplicitID: inputs.implicitID
            )
        }
    }

    nonisolated static func makeForEachViewList(
        view: _GraphValue<Self>,
        inputs: _ViewListInputs
    ) -> _ViewListOutputs? {
        // TODO: Subview stuff
        return nil
    }
}

// MARK: - ForEachEvictionInput

/// Graph input that controls memory eviction behavior for ForEach items.
///
/// ForEach caches view items to optimize performance when data changes.
/// This input determines whether unused items should be evicted from the cache
/// to free memory. Items are evicted when they haven't been accessed recently
/// (determined by time-to-live counters).
///
/// The eviction behavior is controlled by:
/// - A `WeakAttribute<Bool>` that can be set per ForEach instance
/// - A static `evictByDefault` flag based on SDK linking version
package struct ForEachEvictionInput: GraphInput {
    package typealias Value = WeakAttribute<Bool>

    package static let defaultValue: WeakAttribute<Bool> = .init()

    package static let evictByDefault: Bool = isLinkedOnOrAfter(.v6)
}

// MARK: - HasCustomIDRepresentation

/// Protocol for types that provide custom ID matching logic.
///
/// Types conforming to this protocol can implement custom logic for determining
/// if they contain a specific ID value. This is used during ID matching in ForEach
/// when the ID type doesn't exactly match the queried type.
///
/// This enables advanced ID matching scenarios beyond simple equality checks,
/// such as:
/// - Composite IDs that contain multiple sub-IDs
/// - Wrapped ID types that need custom unwrapping logic
/// - ID types with hierarchical relationships
protocol HasCustomIDRepresentation {
    func containsID<ID>(_ id: ID) -> Bool where ID: Hashable
}

// MARK: - LogForEachSlowPath

/// Feature flag for logging when ForEach encounters non-constant view counts.
///
/// When enabled via the user default `-LogForEachSlowPath YES`, this logs
/// warnings when ForEach cannot determine a constant number of views per element.
/// This happens when the view builder contains conditional logic that produces
/// a variable number of views.
///
/// Non-constant view counts prevent optimizations in lazy containers like List
/// and LazyVStack, potentially impacting performance. The logged warnings help
/// developers identify and fix these performance issues.
private struct LogForEachSlowPath: UserDefaultKeyedFeature {    
    static var key: String { "LogForEachSlowPath" }

    static var cachedValue: Bool?

    static var defaults: UserDefaults {
        UserDefaults.openSwiftUI ?? .standard
    }
}

// MARK: - ForEachState

/// Internal state manager for ForEach that coordinates item caching and view generation.
///
/// `ForEachState` is the central coordinator for a ForEach instance. It manages:
///
/// - **Item Cache**: Stores previously created view items by ID for reuse
/// - **View Counts**: Caches the number of views per element for optimization
/// - **Eviction**: Removes unused items from cache based on time-to-live
/// - **Edits**: Tracks insertions/removals for transition animations
/// - **ID Matching**: Provides strategies for matching different ID types
///
/// The state is created during `_makeViewList` and persists across updates to
/// enable efficient view reuse when data changes.
///
/// ## Lifecycle
///
/// 1. Created with `_ViewListInputs` and parent subgraph
/// 2. Updated via `update(view:)` when data changes
/// 3. Creates/reuses `Item` instances via `item(at:offset:)`
/// 4. Evicts unused items via `evictItems(seed:)`
///
/// ## Performance
///
/// - Constant ID types (offset-based) are optimized for minimal overhead
/// - View count caching enables O(1) random access in lazy containers
/// - Eviction prevents unbounded memory growth for long-lived ForEach instances
private class ForEachState<Data, ID, Content> where Data: RandomAccessCollection, ID: Hashable, Content: View {
    let inputs: _ViewListInputs
    let parentSubgraph: Subgraph
    var info: Attribute<Info>?
    var list: Attribute<any ViewList>? = nil
    var view: ForEach<Data, ID, Content>? = nil
    var viewsPerElement: Int?? = nil
    var viewsCounts: [Int] = []
    var viewsCountStyle: ViewList.IteratorStyle = .init()
    var items: [ID: Item] = [:]
    var edits: [ID: ViewList.Edit] = [:]
    var lastTransaction: TransactionID = .init()
    var firstInsertionOffset: Int = -1
    var contentID: Int = 0
    var seed: UInt32 = 0
    var createdAllItems: Bool = false
    var evictionSeed: UInt32 = 0
    var pendingEviction: Bool = false
    var evictedIDs: Set<ID> = .init()
    var matchingStrategyCache: [ObjectIdentifier: IDTypeMatchingStrategy] = [:]

    init(inputs: _ViewListInputs) {
        self.inputs = inputs
        self.parentSubgraph = .current!
    }

    func invalidateViewCounts() {
        viewsCounts.removeAll(keepingCapacity: true)
        viewsCountStyle = .init()
    }

    func update(view: ForEach<Data, ID, Content>) {
        guard parentSubgraph.isValid else {
            return
        }
        contentID = UniqueID().value
        let oldSeed = seed
        seed &+= 1
        invalidateViewCounts()
        if self.view != nil, self.view!.idGenerator.isConstant {
            if self.view!.data.count != view.data.count {
                Log.externalWarning("\(ForEach<Data, ID, Content>.self) count (\(view.data.count)) != its initial count (\(self.view!.data.count)). `ForEach(_:content:)` should only be used for *constant* data. Instead conform data to `Identifiable` or use `ForEach(_:id:content:)` and provide an explicit `id`!")
            }
            let oldData = self.view!.data
            self.view = view
            self.view!.data = oldData
            for (_, item) in items {
                item.contentID = contentID
                if item.seed == oldSeed {
                    item.seed = seed
                }
            }
        } else {
            self.view = view
            edits.removeAll()
            lastTransaction = TransactionID(graph: list!.graph)
            guard firstInsertionOffset >= 0 else {
                firstInsertionOffset = .max
                createdAllItems = false
                return
            }
            var index = view.data.startIndex
            let endIndex = view.data.endIndex
            let itemsCount = items.count
            let evictedIDsCount = evictedIDs.count
            var newEdits = edits
            var newEvictedIDs = Set<ID>()
            firstInsertionOffset = .zero
            var allItemsProcessed = itemsCount == 0
            var remainingItemsCount: Int
            if itemsCount != 0 || evictedIDsCount != 0 {
                remainingItemsCount = itemsCount
                var remainingEvictedIDsCount = evictedIDsCount
                var offset = 0
                while index != endIndex {
                    let idGenerator = view.idGenerator
                    let id = idGenerator.makeID(
                        data: view.data,
                        index: index,
                        offset: offset
                    )
                    let foundActiveItem: Bool
                    if let item = items[id] {
                        firstInsertionOffset = offset
                        item.index = index
                        item.offset = offset
                        item.seed = seed
                        remainingItemsCount &-= 1
                        if item.isRemoved {
                            foundActiveItem = false
                        } else {
                            newEdits = edits
                            foundActiveItem = true
                        }
                    } else {
                        foundActiveItem = false
                    }
                    if evictedIDs.contains(id) {
                        newEvictedIDs.insert(id)
                        remainingEvictedIDsCount &-= 1
                    } else {
                        if !foundActiveItem {
                            edits[id] = .inserted
                        }
                    }
                    view.data.formIndex(after: &index)
                    allItemsProcessed = remainingItemsCount == 0
                    guard remainingItemsCount != 0 || remainingEvictedIDsCount != 0 else {
                        remainingItemsCount = 0
                        allItemsProcessed = true
                        break
                    }
                    offset &+= 1
                }
            } else {
                remainingItemsCount = 0
                allItemsProcessed = true
            }
            if !createdAllItems {
                edits = newEdits
            }
            if !allItemsProcessed {
                var itemsToErase: [Item] = []
                var index = items.startIndex
                let endIndex = items.endIndex
                while index != endIndex {
                    let (_, item) = items[index]
                    if !item.isRemoved, item.seed != seed {
                        itemsToErase.append(item)
                        remainingItemsCount &-= 1
                        edits[item.id] = .removed
                    }
                    items.formIndex(after: &index)
                    guard remainingItemsCount != 0 else {
                        break
                    }
                }
                for item in itemsToErase {
                    eraseItem(item)
                }
            }
            if !createdAllItems {
                firstInsertionOffset = .max
            }
            evictedIDs = newEvictedIDs
            createdAllItems = false
        }
    }

    func item(at index: Data.Index, offset: Int) -> Item {
        let id = view!.idGenerator.makeID(
            data: view!.data,
            index: index,
            offset: offset
        )
        evictedIDs.remove(id)
        guard let item = items[id] else {
            let subgraph = Subgraph(
                graph: parentSubgraph.graph,
                attribute: list!.identifier
            )
            parentSubgraph.addChild(subgraph)
            var childInputs = inputs
            childInputs.base.copyCaches()
            childInputs.implicitID = 0
            childInputs.options.formUnion(.canTransition)
            let (content, accessList) = _withObservation {
                let forEach = view!
                return forEach.content(forEach.data[index])
            }
            var childList: Attribute<any ViewList>?
            let childOutputs = subgraph.apply {
                childInputs.base.pushStableID(id)
                let child = Attribute(
                    ForEachChild(
                        info: info!,
                        id: id
                    )
                )
                child.value = content
                _installObservation(
                    accessLists: accessList.map { [$0] } ?? [],
                    attribute: child
                )
                var outputs = Content.makeDebuggableViewList(
                    view: .init(child),
                    inputs: childInputs
                )
                if inputs.options.contains(.needsDynamicTraits) {
                    let itemList = Attribute(
                        ItemList(
                            base: outputs.makeAttribute(inputs: inputs),
                            item: nil
                        )
                    )
                    childList = itemList
                    itemList.addInput(list!, options: [._4], token: 0)
                    outputs.views = .dynamicList(childList!, nil)
                }
                return outputs
            }
            let item = Item(
                id: id,
                reuseID: view!.reuseID.map {
                    view!.data[index][keyPath: $0]
                } ?? Int(bitPattern: ObjectIdentifier(Content.self)),
                views: childOutputs.views,
                subgraph: subgraph,
                index: index,
                offset: offset,
                contentID: contentID,
                seed: seed,
                state: self,
                isConstant: view!.idGenerator.isConstant
            )
            items[id] = item
            if let childList {
                childList.mutateBody(
                    as: ItemList.self,
                    invalidating: true
                ) { itemList in
                    itemList.item = item
                }
            }
            if firstInsertionOffset <= offset {
                edits[item.id] = .inserted
            }
            if viewsPerElement == nil {
                let staticCount = childOutputs.staticCount
                if let staticCount {
                    viewsPerElement = staticCount
                } else {
                    viewsPerElement = Content._viewListCount(inputs: .init(childInputs))
                    if LogForEachSlowPath.isEnabled,
                       inputs.isInLazyContainer,
                       let viewsPerElement,
                       viewsPerElement == nil {
                        Log.externalWarning("Unable to determine number of views per element in the collection \(Data.self). If this view only produces one view per element in the collection, consider wrapping your views in a VStack to take the fast path.")
                    }
                }
            }
            return item
        }
        if item.isRemoved {
            uneraseItem(item)
        }
        if item.seed == seed {
            if !item.hasWarned, item.index != index, isLinkedOnOrAfter(.v3) {
                item.hasWarned = true
                Log.externalWarning(
                    "\(ForEach<Data, ID, Content>.self): the ID" +
                    " occurs multiple times within the collection, this will give undefined results!"
                )
            }
        } else {
            item.index = index
            item.offset = offset
            item.contentID = contentID
            item.seed = seed
        }
        item.timeToLive = 8
        return item
    }

    func eraseItem(_ item: Item) {
        item.subgraph.willRemove()
        parentSubgraph.removeChild(item.subgraph)
        item.isRemoved = true
        item.timeToLive = 0
        item.invalidate(isInserted: true)
    }

    func uneraseItem(_ item: Item) {
        item.retain()
        item.isRemoved = false
        item.timeToLive = 8
        parentSubgraph.addChild(item.subgraph)
        item.subgraph.didReinsert()
    }

    func evictItems(seed: UInt32) {
        guard evictionSeed != seed, !pendingEviction else { return }
        evictionSeed = seed
        var evictItems: [Item] = []

        let startIndex = items.startIndex
        let endIndex = items.endIndex
        let pendingEviction: Bool
        if startIndex != endIndex {
            var index = startIndex
            var remainingEvictions = 64
            while true {
                let (id, item) = items[index]
                if !item.isRemoved {
                    let timeToLive = item.timeToLive - 1
                    if timeToLive == 0 {
                        if item.refcount == 1 {
                            evictItems.append(item)
                            evictedIDs.insert(id)
                            remainingEvictions &-= 1
                        }
                    } else {
                        item.timeToLive = timeToLive
                    }
                }
                items.formIndex(after: &index)
                guard remainingEvictions >= 1 else {
                    break
                }
                guard index != endIndex else {
                    remainingEvictions = 64
                    break
                }
            }
            pendingEviction = remainingEvictions == 0
        } else {
            pendingEviction = false
        }
        for evictItem in evictItems {
            eraseItem(evictItem)
        }
        self.pendingEviction = pendingEviction
    }

    func fetchViewsPerElement() -> Int? {
        if let viewsPerElement {
            return viewsPerElement
        } else {
            guard !view!.data.isEmpty else {
                return nil
            }
            _ = item(at: view!.data.startIndex, offset: 0)
            return viewsPerElement ?? nil
        }
    }

    @discardableResult
    func applyNodes(
        from start: inout Int,
        style: ViewList.IteratorStyle,
        list: Attribute<any ViewList>?,
        transform: inout ViewList.SublistTransform,
        to body: ViewList.ApplyBody
    ) -> Bool {
        forEachItem(
            from: &start,
            style: style
        ) {
            start,
            style,
            item in
            let idGenerator = view!.idGenerator
            switch item.views {
            case let .staticList(elements):
                let elementsCount = elements.count
                let count = style.applyGranularity(to: elementsCount)
                guard start < count else {
                    start &-= count
                    return true
                }
                var id = ViewList.ID()
                if idGenerator.isConstant {
                    let owner = list!.identifier
                    let explicitID = Pair(item.offset, owner)
                    id.bind(
                        explicitID: explicitID,
                        owner: owner,
                        isUnary: viewsPerElement == 1,
                        reuseID: item.reuseID
                    )
                } else {
                    id.bind(
                        explicitID: item.id,
                        owner: list!.identifier,
                        isUnary: viewsPerElement == 1,
                        reuseID: item.reuseID
                    )
                }
                let sublist = ViewList.Sublist(
                    start: start,
                    count: elementsCount,
                    id: id,
                    elements: elements,
                    traits: .init(),
                    list: nil
                )
                let transformItem = Transform(
                    item: item,
                    bindID: false,
                    isUnary: viewsPerElement == 1,
                    isConstant: idGenerator.isConstant
                )
                transform.push(transformItem)
                let result = body(&start, style, .sublist(sublist), &transform)
                transform.pop()
                start = 0
                return result
            case let .dynamicList(attribute, listModifier):
                var viewList = RuleContext(attribute: list!)[attribute]
                if let listModifier {
                    listModifier.apply(to: &viewList)
                }
                let transformItem = Transform(
                    item: item,
                    bindID: true,
                    isUnary: viewsPerElement == 1,
                    isConstant: idGenerator.isConstant
                )
                transform.push(transformItem)
                let result = viewList.applyNodes(
                    from: &start,
                    style: style,
                    list: attribute,
                    transform: &transform,
                    to: body
                )
                transform.pop()
                return result
            }
        }
    }

    @discardableResult
    func forEachItem(
        from start: inout Int,
        style: ViewList.IteratorStyle,
        do body: (inout Int, ViewList.IteratorStyle, Item) -> Bool
    ) -> Bool {
        guard parentSubgraph.isValid else { return true }
        let endIndex = view!.data.endIndex
        var index = view!.data.startIndex
        var offset: Int
        if start >= 1 {
            if let perElement = fetchViewsPerElement() {
                let count = style.applyGranularity(to: perElement)
                if start >= count {
                    offset = min(view!.data.count, count < 2 ? start : start / count)
                    view!.data.formIndex(&index, offsetBy: offset)
                    start &-= count * offset
                } else {
                    offset = 0
                }
            } else {
                if !viewsCounts.isEmpty, viewsCountStyle == style {
                    offset = viewsCounts.lowerBound { start >= $0 }
                    view!.data.formIndex(&index, offsetBy: offset)
                    if offset >= 1 {
                        start &-= viewsCounts[offset-1]
                    }
                } else {
                    offset = 0
                }
            }
        } else {
            offset = 0
        }
        while index != endIndex {
            let item = item(at: index, offset: offset)
            guard body(&start, style, item) else {
                return false
            }
            view!.data.formIndex(after: &index)
            offset += 1
        }
        createdAllItems = true
        return true
    }

    func count(
        style: ViewList.IteratorStyle
    ) -> Int {
        guard parentSubgraph.isValid else {
            return 0
        }
        let count = view!.data.count
        guard count != 0 else {
            return 0
        }
        if let perElement = fetchViewsPerElement() {
            return style.applyGranularity(to: perElement * count)
        } else {
            if viewsCounts.count >= count, viewsCountStyle == style {
                return viewsCounts[count-1]
            } else {
                var count = 0
                var vcc = 0
                var start = 0
                forEachItem(
                    from: &start,
                    style: .init()
                ) { _, _, item in
                    switch item.views {
                    case let .staticList(elements):
                        count += style.applyGranularity(to: elements.count)
                    case let .dynamicList(attribute, _):
                        let viewList = RuleContext(attribute: list!)[attribute]
                        count += viewList.count
                    }
                    let viewsCountsCount = viewsCounts.count
                    if viewsCountsCount == 0 || (viewsCountsCount == vcc && viewsCountStyle == style) {
                        viewsCounts.append(count)
                        viewsCountStyle = style
                    }
                    vcc &+= 1
                    return true
                }
                return count
            }
        }
    }

    func estimatedCount(
        style: ViewList.IteratorStyle
    ) -> Int {
        guard parentSubgraph.isValid else {
            return 0
        }
        let count = view!.data.count
        guard count != 0 else {
            return 0
        }
        if let perElement = fetchViewsPerElement() {
            return style.applyGranularity(to: perElement * count)
        } else {
            if viewsCounts.count >= count, viewsCountStyle == style {
                // [Q]: Why we need apply on estimatedCount while not on count?
                return style.applyGranularity(to: viewsCounts[count-1])
            } else {
                var usedItemCount = 0 // 198
                var totalCount = 0 // 1a0
                for (_, item) in items {
                    guard item.seed == seed else {
                        continue
                    }
                    usedItemCount += 1
                    switch item.views {
                    case let .staticList(elements):
                        totalCount += style.applyGranularity(to: elements.count)
                    case let .dynamicList(attribute, _):
                        let viewList = RuleContext(attribute: list!)[attribute]
                        totalCount += viewList.estimatedCount(style: style)
                    }
                }
                let unusedItemCount = view!.data.count - usedItemCount
                guard unusedItemCount >= 1 else {
                    return totalCount
                }
                guard usedItemCount >= 1 else {
                    return totalCount + unusedItemCount
                }
                let unusedEstimate = Int(ceil(Double(totalCount) / Double(usedItemCount) * Double(unusedItemCount)))
                return totalCount + unusedEstimate
            }
        }
    }

    func edit(
        forID id: ViewList.ID,
        since transaction: TransactionID
    ) -> ViewList.Edit? {
        switch view!.idGenerator {
        case .keyPath:
            guard let explicitID: ID = id.explicitID(owner: list!.identifier) else {
                return nil
            }
            if transaction >= lastTransaction, let edit = edits[explicitID] {
                return edit
            }
            guard let item = items[explicitID], item.seed == seed else {
                return nil
            }
            switch item.views {
            case .staticList:
                return nil
            case let .dynamicList(attribute, _):
                let viewList = RuleContext(attribute: list!)[attribute]
                return viewList.edit(forID: id, since: transaction)
            }
        case .offset:
            return nil
        }
    }

    func matchingStrategy<T>(
        for type: T.Type
    ) -> IDTypeMatchingStrategy where T: Hashable {
        let id = ObjectIdentifier(type)
        if let strategy = matchingStrategyCache[id] {
            return strategy
        }
        let strategy: IDTypeMatchingStrategy
        switch view!.idGenerator {
        case .keyPath:
            if ID.self == T.self {
                strategy = .exact
            } else {
                if isLinkedOnOrAfter(.v6), ID.self == AnyHashable.self {
                    strategy = .anyHashable
                } else if isLinkedOnOrAfter(.v6), ID.self is HasCustomIDRepresentation {
                    strategy = .customIDRepresentation
                } else {
                    strategy = .noMatch
                }
            }
        case .offset:
            strategy = .noMatch
        }
        matchingStrategyCache[id] = strategy
        return strategy
    }

    func firstOffset<OtherID>(
        forID id: OtherID,
        style: ViewList.IteratorStyle
    ) -> Int? where OtherID: Hashable {
        guard parentSubgraph.isValid else {
            return nil
        }
        let strategy = matchingStrategy(for: OtherID.self)
        var firstOffset: Int?
        var count = 0
        var start = 0
        forEachItem(
            from: &start,
            style: style
        ) { _, style, item in
            var nonOptionalFirstOffset = 0
            let match: Bool
            switch strategy {
            case .exact, .anyHashable:
                let itemID = item.id as? OtherID
                match = id == itemID
            case .customIDRepresentation:
                let custom = item.id as! HasCustomIDRepresentation
                match = custom.containsID(id)
            case .noMatch:
                match = false
            }
            if !match {
                guard case let .dynamicList(attribute, _) = item.views else {
                    count &+= 1
                    return true
                }
                let viewList = RuleContext(attribute: list!)[attribute]
                guard let offset = viewList.firstOffset(forID: id, style: style) else {
                    count &+= 1
                    return true
                }
                nonOptionalFirstOffset = offset
            }
            if count != 0 {
                if let perElement = fetchViewsPerElement() {
                    nonOptionalFirstOffset += count * style.applyGranularity(to: perElement)
                } else {
                    if viewsCounts.count >= count, viewsCountStyle == style {
                        nonOptionalFirstOffset += viewsCounts[count-1]
                    } else {
                        var subCount = 0
                        var subStart = 0
                        forEachItem(
                            from: &subStart,
                            style: style
                        ) { _, style, item in
                            guard subCount != count else {
                                return false
                            }
                            subCount &+= 1
                            switch item.views {
                            case let .staticList(elements):
                                nonOptionalFirstOffset += style.applyGranularity(to: elements.count)
                            case let .dynamicList(attribute, _):
                                let viewList = RuleContext(attribute: list!)[attribute]
                                nonOptionalFirstOffset += viewList.count
                            }
                            return true
                        }
                    }
                }
            }
            firstOffset = nonOptionalFirstOffset
            return false
        }
        return firstOffset
    }

    var traitKeys: ViewTraitKeys? {
        var traitKeys: ViewTraitKeys?
        var start = 0
        forEachItem(
            from: &start,
            style: .init()
        ) { _, _, item in
            switch item.views {
            case .staticList:
                traitKeys = .init()
            case let .dynamicList(attribute, _):
                let viewList = RuleContext(attribute: list!)[attribute]
                traitKeys = viewList.traitKeys
            }
            return false
        }
        guard let traitKeys else {
            return nil
        }
        return traitKeys.isDataDependent ? nil : traitKeys
    }

    var viewIDs: ViewList.ID.Views? {
        guard parentSubgraph.isValid,
              let perElement = fetchViewsPerElement()
        else {
            return nil
        }
        var start = 0
        var viewIDs: ViewList.ID.Views?
        forEachItem(
            from: &start,
            style: .init()
        ) { _, _, item in
            switch item.views {
            case .staticList:
                let base = StaticViewIDCollection(count: perElement)
                viewIDs = ViewList.ID._Views(base, isDataDependent: false)
            case let .dynamicList(attribute, _):
                let viewList = RuleContext(attribute: list!)[attribute]
                viewIDs = viewList.viewIDs
            }
            return false
        }
        guard let viewIDs,
              !viewIDs.isDataDependent
        else {
            return nil
        }
        let idCollection = ForEachViewIDCollection(
            base: viewIDs,
            data: view!.data,
            idGenerator: view!.idGenerator,
            reuseID: view!.reuseID,
            isUnary: perElement == 1,
            owner: list!.identifier
        )
        return ViewList.ID._Views(idCollection, isDataDependent: true)
    }

    // MARK: - ForEachState.Item

    /// Cached view item for a single element in the ForEach data collection.
    ///
    /// Each `Item` represents one element from the ForEach's data, containing:
    /// - The generated view hierarchy (`views`)
    /// - Identity information (`id`, `reuseID`)
    /// - Position tracking (`index`, `offset`)
    /// - Lifecycle state (`seed`, `timeToLive`, `isRemoved`)
    ///
    /// Items are retained in `ForEachState.items` and reused across updates when
    /// their ID matches. This enables efficient view updates and smooth transitions.
    ///
    /// ## Memory Management
    ///
    /// - `timeToLive`: Decremented each eviction cycle; removed when zero
    /// - `refcount`: Reference count for subgraph lifecycle
    /// - `isRemoved`: Marks items for cleanup without immediate invalidation
    class Item: ViewList.Subgraph {
        let id: ID
        let reuseID: Int
        let views: _ViewListOutputs.Views
        weak var state: ForEachState? = nil
        var index: Data.Index
        var offset: Int
        var contentID: Int
        var seed: UInt32
        var isConstant: Bool
        var timeToLive: Int8 = 8
        var isRemoved: Bool = false
        var hasWarned: Bool = false

        init(
            id: ID,
            reuseID: Int,
            views: _ViewListOutputs.Views,
            subgraph: Subgraph,
            index: Data.Index,
            offset: Int,
            contentID: Int,
            seed: UInt32,
            state: ForEachState?,
            isConstant: Bool
        ) {
            self.id = id
            self.reuseID = reuseID
            self.views = views
            self.state = state
            self.index = index
            self.offset = offset
            self.contentID = contentID
            self.seed = seed
            self.isConstant = isConstant
            super.init(subgraph: subgraph)
        }

        override func invalidate() {
            guard let state else {
                return
            }
            if let index = state.items.index(forKey: id) {
                state.items.remove(at: index)
            } else {
                state.items = state.items.filter { (key, value) in
                    value !== self
                }
            }
        }

        func applyTraits(to collection: inout ViewTraitCollection) {
            collection.setValueIfUnset(contentID, for: DynamicViewContentIDTraitKey.self)
            collection.setValueIfUnset(offset, for: DynamicViewContentOffsetTraitKey.self)
            if isConstant {
                collection.setTagIfUnset(for: Int.self, value: offset)
            } else {
                collection.setTagIfUnset(for: ID.self, value: id)
            }
        }
    }

    // MARK: - ForEachState.IDTypeMatchingStrategy

    enum IDTypeMatchingStrategy {
        case exact
        case anyHashable
        case customIDRepresentation
        case noMatch
    }

    // MARK: - Evictor

    /// Rule that performs periodic eviction of unused ForEach items.
    ///
    /// The `Evictor` runs as an async attribute that monitors the update seed
    /// and evicts cached items that haven't been used recently. This prevents
    /// unbounded memory growth in long-lived ForEach instances.
    ///
    /// Eviction behavior:
    /// - Triggered when `updateSeed` changes
    /// - Evicts up to 64 items per cycle
    /// - Only evicts items with `timeToLive == 0` and `refcount == 1`
    /// - Evicted IDs are tracked to prevent immediate recreation
    struct Evictor: Rule, AsyncAttribute {
        var state: ForEachState
        @WeakAttribute var isEnabled: Bool?
        @Attribute var updateSeed: UInt32

        var value: Void {
            if isEnabled ?? ForEachEvictionInput.evictByDefault {
                state.evictItems(seed: updateSeed)
            }
        }
    }

    // MARK: - Info

    /// Wrapper for ForEachState that tracks the current update seed.
    ///
    /// `Info` provides a value-type interface to the reference-type `ForEachState`.
    /// It captures the state's seed at the time of creation, allowing downstream
    /// code to detect when the state has been updated.
    struct Info {
        var state: ForEachState
        var seed: UInt32

        struct Init: Rule, CustomStringConvertible {
            @Attribute var view: ForEach<Data, ID, Content>
            let state: ForEachState

            var value: Info {
                state.update(view: view)
                return Info(state: state, seed: state.seed)
            }

            var description: String {
                "Collection.Info"
            }
        }
    }

    // MARK: - StaticViewIDCollection

    struct StaticViewIDCollection: RandomAccessCollection, Equatable {
        var count: Int

        var startIndex: Int { 0 }

        var endIndex: Int { count }

        subscript(position: Int) -> ViewList.ID {
            _read {
                yield ViewList.ID().elementID(at: position)
            }
        }
    }

    // MARK: - ForEachViewIDCollection

    struct ForEachViewIDCollection: RandomAccessCollection, Equatable {
        var base: ViewList.ID.Views
        var data: Data
        var idGenerator: ForEach<Data, ID, Content>.IDGenerator
        var reuseID: KeyPath<Data.Element, Int>?
        var isUnary: Bool
        var owner: AnyAttribute
        var baseCount: Int
        var count: Int

        init(
            base: ViewList.ID.Views,
            data: Data,
            idGenerator: ForEach<Data, ID, Content>.IDGenerator,
            reuseID _: KeyPath<Data.Element, Int>?,
            isUnary: Bool,
            owner: AnyAttribute
        ) {
            self.base = base
            self.data = data
            self.idGenerator = idGenerator
            self.isUnary = isUnary
            self.owner = owner
            let endIndex = base.endIndex
            baseCount = endIndex
            count = data.count * endIndex
        }

        var startIndex: Int { 0 }

        var endIndex: Int { count }

        subscript(position: Int) -> ViewList.ID {
            _read {
                let dataOffset = position / baseCount
                let baseIndex = position - dataOffset * baseCount
                var id = base[baseIndex]
                let dataIndex = data.index(data.startIndex, offsetBy: dataOffset)
                let reuseID = reuseID.map { keyPath in
                    data[dataIndex][keyPath: keyPath]
                } ?? Int(bitPattern: ObjectIdentifier(Content.self))
                if idGenerator.isConstant {
                    let explicitID = Pair(dataOffset, owner)
                    id.bind(
                        explicitID: explicitID,
                        owner: owner,
                        isUnary: isUnary,
                        reuseID: reuseID
                    )
                } else {
                    let explicitID = idGenerator.makeID(
                        data: data,
                        index: dataIndex,
                        offset: dataOffset
                    )
                    id.bind(
                        explicitID: explicitID,
                        owner: owner,
                        isUnary: isUnary,
                        reuseID: reuseID
                    )
                }
                yield id
            }
        }

        static func == (
            lhs: ForEachViewIDCollection,
            rhs: ForEachViewIDCollection
        ) -> Bool {
            lhs.base == rhs.base &&
            lhs.isUnary == rhs.isUnary &&
            lhs.owner == rhs.owner &&
            compareValues(lhs.data, rhs.data)
        }
    }

    // MARK: - Transform

    struct Transform: ViewList.SublistTransform.Item {
        var item: Item
        var bindID: Bool
        var isUnary: Bool
        var isConstant: Bool

        func apply(sublist: inout ViewList.Sublist) {
            bindID(&sublist.id)
            sublist.elements = item.wrapping(sublist.elements)
            item.applyTraits(to: &sublist.traits)
        }

        func bindID(_ id: inout ViewList.ID) {
            guard bindID,
                  let state = item.state,
                  let list = state.list
            else {
                return
            }
            if isConstant {
                let explicitID = Pair(item.offset, list.identifier)
                id.bind(
                    explicitID: explicitID,
                    owner: list.identifier,
                    isUnary: isUnary,
                    reuseID: item.reuseID
                )
            } else {
                id.bind(
                    explicitID: item.id,
                    owner: list.identifier,
                    isUnary: isUnary,
                    reuseID: item.reuseID
                )
            }
        }
    }

    // MARK: - ItemList

    struct ItemList: Rule {
        @Attribute var base: any ViewList
        var item: Item?

        var value: any ViewList {
            WrappedList(base: base, item: item)
        }

        struct WrappedList: ViewList {
            var base: any ViewList
            var item: Item?

            func count(style: IteratorStyle) -> Int {
                base.count(style: style)
            }

            func estimatedCount(style: IteratorStyle) -> Int {
                base.estimatedCount(style: style)
            }

            var traitKeys: ViewTraitKeys? {
                base.traitKeys
            }

            var viewIDs: ViewList.ID.Views? {
                base.viewIDs
            }

            var traits: ViewTraitCollection {
                var traits = base.traits
                if let item {
                    item.applyTraits(to: &traits)
                }
                return traits
            }

            @discardableResult
            func applyNodes(
                from start: inout Int,
                style: IteratorStyle,
                list: Attribute<any ViewList>?,
                transform: inout SublistTransform,
                to body: ApplyBody
            ) -> Bool {
                base.applyNodes(
                    from: &start,
                    style: style,
                    list: list,
                    transform: &transform,
                    to: body
                )
            }

            func edit(
                forID id: ViewList.ID,
                since transaction: TransactionID
            ) -> Edit? {
                base.edit(forID: id, since: transaction)
            }

            func firstOffset<OtherID>(
                forID id: OtherID,
                style: IteratorStyle
            ) -> Int? where OtherID: Hashable {
                base.firstOffset(forID: id, style: style)
            }
        }
    }
}

// MARK: - ForEachChild

/// View wrapper that generates content for a single ForEach element.
///
/// `ForEachChild` is a `StatefulRule` that creates and updates the view for one
/// element in the ForEach's data collection. It uses observation to track access
/// to the data element and automatically updates when the data changes.
///
/// The child is identified by its `id` and retrieves the current data element
/// from `ForEachState` based on this ID. This indirection allows the same child
/// to be reused even when the element's position in the collection changes.
///
/// ## Update Behavior
///
/// - Validates that the item still exists in the state
/// - Checks that the item's seed matches the current state seed
/// - Re-evaluates the content closure with the current data element
/// - Installs observation to track data access
private struct ForEachChild<Data, ID, Content>: StatefulRule, CustomStringConvertible where Data: RandomAccessCollection, ID: Hashable, Content: View {
    @Attribute var info: ForEachState<Data, ID, Content>.Info
    let id: ID

    typealias Value = Content

    func updateValue() {
        let state = info.state
        guard let item = state.items[id],
              item.seed == state.seed else {
            return
        }
        value = withObservation {
            let forEach = state.view!
            return forEach.content(forEach.data[item.index])
        }
    }

    var description: String {
        "Collection[\(id)]"
    }
}

// MARK: - ForEachList

/// ViewList implementation that provides the view hierarchy for a ForEach.
///
/// `ForEachList` conforms to the `ViewList` protocol and delegates all operations
/// to the underlying `ForEachState`. It serves as the reactive bridge between
/// the attribute graph and the state management layer.
///
/// The list is created via `Init` which sets up observation on the state's `Info`.
/// When the info changes (indicating the ForEach data has updated), the list
/// increments its seed and invalidates cached view counts, triggering a refresh.
///
/// ## Delegation Pattern
///
/// All ViewList protocol methods delegate to `ForEachState`:
/// - `count`, `estimatedCount` → state item iteration
/// - `applyNodes` → state's node application with transforms
/// - `edit`, `firstOffset` → state's edit tracking and ID lookup
/// - `traitKeys`, `viewIDs` → state's metadata computation
private struct ForEachList<Data, ID, Content>: ViewList where Data: RandomAccessCollection, ID: Hashable, Content: View {
    var state: ForEachState<Data, ID, Content>
    var seed: UInt32

    func count(style: IteratorStyle) -> Int {
        state.count(style: style)
    }

    func estimatedCount(style: IteratorStyle) -> Int {
        state.estimatedCount(style: style)
    }

    var traitKeys: ViewTraitKeys? {
        state.traitKeys
    }

    var viewIDs: ViewList.ID.Views? {
        state.viewIDs
    }

    var traits: ViewTraitCollection {
        .init()
    }

    @discardableResult
    func applyNodes(
        from start: inout Int,
        style: IteratorStyle,
        list: Attribute<any ViewList>?,
        transform: inout SublistTransform,
        to body: ApplyBody
    ) -> Bool {
        state.applyNodes(
            from: &start,
            style: style,
            list: list,
            transform: &transform,
            to: body
        )
    }

    func edit(
        forID id: ViewList.ID,
        since transaction: TransactionID
    ) -> Edit? {
        state.edit(forID: id, since: transaction)
    }

    func firstOffset<OtherID>(
        forID id: OtherID,
        style: IteratorStyle
    ) -> Int? where OtherID: Hashable {
        state.firstOffset(forID: id, style: style)
    }

    struct Init: StatefulRule, AsyncAttribute, CustomStringConvertible {
        @Attribute var info: ForEachState<Data, ID, Content>.Info
        var seed: UInt32

        typealias Value = any ViewList

        mutating func updateValue() {
            info.state.invalidateViewCounts()
            seed &+= 1
            value = ForEachList(state: info.state, seed: seed)
        }

        var description: String {
            "Collection.List"
        }
    }
}

// MARK: - ForEach + id

@available(OpenSwiftUI_v1_0, *)
extension ForEach where ID == Data.Element.ID, Content: View, Data.Element: Identifiable {

    /// Creates an instance that uniquely identifies and creates views across
    /// updates based on the identity of the underlying data.
    ///
    /// It's important that the `id` of a data element doesn't change unless you
    /// replace the data element with a new data element that has a new
    /// identity. If the `id` of a data element changes, the content view
    /// generated from that data element loses any current state and animations.
    ///
    /// - Parameters:
    ///   - data: The identified data that the ``ForEach`` instance uses to
    ///     create views dynamically.
    ///   - content: The view builder that creates views dynamically.
    public init(_ data: Data, @ViewBuilder content: @escaping (Data.Element) -> Content) {
        self.init(data, idGenerator: .keyPath(\.id), content: content)
    }
}

@available(OpenSwiftUI_v1_0, *)
extension ForEach where Content: View {

    /// Creates an instance that uniquely identifies and creates views across
    /// updates based on the provided key path to the underlying data's
    /// identifier.
    ///
    /// It's important that the `id` of a data element doesn't change, unless
    /// SwiftUI considers the data element to have been replaced with a new data
    /// element that has a new identity. If the `id` of a data element changes,
    /// then the content view generated from that data element will lose any
    /// current state and animations.
    ///
    /// - Parameters:
    ///   - data: The data that the ``ForEach`` instance uses to create views
    ///     dynamically.
    ///   - id: The key path to the provided data's identifier.
    ///   - content: The view builder that creates views dynamically.
    public init(
        _ data: Data,
        id: KeyPath<Data.Element, ID>,
        @ViewBuilder content: @escaping (Data.Element) -> Content
    ) {
        self.init(
            data,
            idGenerator: .keyPath(id),
            content: content
        )
    }
}

// MARK: - ForEach + binding

@available(OpenSwiftUI_v1_0, *)
extension ForEach where Content: View {

    /// Creates an instance that uniquely identifies and creates views across
    /// updates based on the identity of the underlying data.
    ///
    /// It's important that the `id` of a data element doesn't change unless you
    /// replace the data element with a new data element that has a new
    /// identity. If the `id` of a data element changes, the content view
    /// generated from that data element loses any current state and animations.
    ///
    /// - Parameters:
    ///   - data: The identified data that the ``ForEach`` instance uses to
    ///     create views dynamically.
    ///   - content: The view builder that creates views dynamically.
    @_disfavoredOverload
    @_alwaysEmitIntoClient
    public init<C>(
        _ data: Binding<C>,
        @ViewBuilder content: @escaping (Binding<C.Element>) -> Content
    ) where Data == LazyMapSequence<C.Indices, (C.Index, ID)>,
    ID == C.Element.ID,
    C: MutableCollection,
    C: RandomAccessCollection,
    C.Element: Identifiable,
    C.Index: Hashable {
        self.init(data, id: \.id, content: content)
    }

    /// Creates an instance that uniquely identifies and creates views across
    /// updates based on the identity of the underlying data.
    ///
    /// It's important that the `id` of a data element doesn't change unless you
    /// replace the data element with a new data element that has a new
    /// identity. If the `id` of a data element changes, the content view
    /// generated from that data element loses any current state and animations.
    ///
    /// - Parameters:
    ///   - data: The identified data that the ``ForEach`` instance uses to
    ///     create views dynamically.
    ///   - id: The key path to the provided data's identifier.
    ///   - content: The view builder that creates views dynamically.
    @_disfavoredOverload
    @_alwaysEmitIntoClient
    public init<C>(
        _ data: Binding<C>,
        id: KeyPath<C.Element, ID>,
        @ViewBuilder content: @escaping (Binding<C.Element>) -> Content
    ) where Data == LazyMapSequence<C.Indices, (C.Index, ID)>,
    C: MutableCollection,
    C: RandomAccessCollection,
    C.Index: Hashable {
        let elementIDs = data.wrappedValue.indices.lazy.map { index in
            (index, data.wrappedValue[index][keyPath: id])
        }
        self.init(elementIDs, id: \.1) { (index, _) in
            let elementBinding = Binding {
                data.wrappedValue[index]
            } set: {
                data.wrappedValue[index] = $0
            }
            content(elementBinding)
        }
    }
}

// MARK: - ForEach + range

@available(OpenSwiftUI_v1_0, *)
extension ForEach where Data == Range<Int>, ID == Int, Content: View {

    /// Creates an instance that computes views on demand over a given constant
    /// range.
    ///
    /// The instance only reads the initial value of the provided `data` and
    /// doesn't need to identify views across updates. To compute views on
    /// demand over a dynamic range, use ``ForEach/init(_:id:content:)``.
    ///
    /// - Parameters:
    ///   - data: A constant range.
    ///   - content: The view builder that creates views dynamically.
    @_semantics("openswiftui.requires_constant_range")
    // NOTE: Use this to make Xcode Swift Toolchain emit warning for non-constant ranges. eg. "Non-constant range: not an integer range"
    @_semantics("swiftui.requires_constant_range")
    public init(_ data: Range<Int>, @ViewBuilder content: @escaping (Int) -> Content) {
        self.init(data, idGenerator: .offset, content: content)
    }
}
